package leetcode.backtrace;

import java.util.Stack;

/**
 * @Description
 * @Author 26233
 * @Create 2021-04-17 21:29:44
 */

/*

在给定的二维二进制数组 A 中，存在两座岛。（岛是由四面相连的 1 形成的一个最大组。）

现在，我们可以将 0 变为 1，以使两座岛连接起来，变成一座岛。

返回必须翻转的 0 的最小数目。（可以保证答案至少是 1 。）

 

示例 1：

输入：A = [[0,1],[1,0]]
输出：1
示例 2：

输入：A = [[0,1,0],[0,0,0],[0,0,1]]
输出：2
示例 3：

输入：A = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
输出：1
 

提示：

2 <= A.length == A[0].length <= 100
A[i][j] == 0 或 A[i][j] == 1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shortest-bridge
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。


 */

public class LeetCode934_ShortestBridge {

    public int shortestBridge(int[][] A) {

        boolean flag = false;
        int[][] visited = new int[A.length][A[0].length];
        Stack<int[]> stack = new Stack<>();

        for (int i = 0; i < A.length; i++) {
            if (flag) break;
            for (int j = 0; j < A[0].length; j++) {
                if (A[i][j] == 1){
                    // dfs 搜索出一个岛
                    shortestBridge(A, i, j, visited, stack);
                    flag = true;
                    break;
                }
            }
        }

        // bfs 找最短距离
        Stack<int[]> tempStack = new Stack<>();
        int count = 0;
        while(true) {
            if (!flag) break;
            while (!stack.isEmpty()) {
                int[] t = stack.pop();

                // 修改原始数组的A[i][j] = 2;
                if (A[t[0]][t[1]] == 1) {
                    flag = false;
                    count--;
                    break;
                }

                if (t[0] - 1 >= 0 && visited[t[0] - 1][t[1]] != 1) {
                    visited[t[0] - 1][t[1]] = 1;
                    tempStack.add(new int[]{t[0] - 1, t[1]});
                }
                if (t[0] + 1 < A.length && visited[t[0] + 1][t[1]] != 1) {
                    visited[t[0] + 1][t[1]] = 1;
                    tempStack.add(new int[]{t[0] + 1, t[1]});
                }
                if (t[1] - 1 >= 0 && visited[t[0]][t[1] - 1] != 1) {
                    visited[t[0]][t[1] - 1] = 1;
                    tempStack.add(new int[]{t[0], t[1] - 1});
                }
                if (t[1] + 1 < A[0].length && visited[t[0]][t[1] + 1] != 1) {
                    visited[t[0]][t[1] + 1] = 1;
                    tempStack.add(new int[]{t[0], t[1] + 1});
                }

            }
            stack.addAll(tempStack);
            tempStack.clear();
            count++;
        }

        return count - 1;

    }

    public void shortestBridge(int[][] A, int i, int j, int[][] visited, Stack<int[]> stack) {
        if (i >= 0 && i < A.length && j >= 0 && j < A[0].length && visited[i][j] != 1){
            if (A[i][j] == 1){
                stack.add(new int[]{i, j});

                A[i][j] = 2;
                visited[i][j] = 1;
                shortestBridge(A, i - 1, j, visited, stack);
                shortestBridge(A, i + 1, j, visited, stack);
                shortestBridge(A, i, j - 1, visited, stack);
                shortestBridge(A, i, j + 1, visited, stack);
            }
        }
    }


    public static void main(String[] args) {
        int[][] A = {
                {1,1,1,1,1},
                {1,0,0,0,1},
                {1,0,1,0,1},
                {1,0,0,0,1},
                {1,1,1,1,1}};


        int i = new LeetCode934_ShortestBridge().shortestBridge(A);

        System.out.println("A = " + A);
    }

}

